package com.googlecode.gaal.analysis.impl;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;

import com.googlecode.gaal.analysis.api.Filter;
import com.googlecode.gaal.analysis.api.IntervalSetBuilder;
import com.googlecode.gaal.data.api.SymbolTable;
import com.googlecode.gaal.suffix.api.EmbeddedSuffixTree.EmbeddedInterval;
import com.googlecode.gaal.suffix.api.IntervalTree.Interval;
import com.googlecode.gaal.suffix.api.LinearizedSuffixTree;

public class RecursiveIntervalExtractor implements Iterable<Interval> {
    private final EmbeddedIntervalExtractor intervalExtractor;
    private final LinearizedSuffixTree lst;
    private final IntervalSetBuilder intervalSetBuilder;

    public RecursiveIntervalExtractor(LinearizedSuffixTree lst, SymbolTable<?> symbolTable,
            IntervalSetBuilder intervalSetBuilder, Filter<EmbeddedInterval> contextFilter, int windowSize) {
        this.intervalExtractor = new EmbeddedIntervalExtractor(lst, symbolTable, intervalSetBuilder, contextFilter,
                windowSize);
        this.intervalSetBuilder = intervalSetBuilder;
        this.lst = lst;
    }

    @Override
    public Iterator<Interval> iterator() {
        return new RecursiveIntervalIterator(-1, -1);
    }

    public Iterator<Interval> iterator(int depth, int maxDepth) {
        return new RecursiveIntervalIterator(depth, maxDepth);
    }

    private class RecursiveIntervalIterator implements Iterator<Interval> {
        private Iterator<? extends Interval> iterator = intervalSetBuilder.buildIntervalSet(lst).iterator();
        private final Deque<Iterator<? extends Interval>> stack = new ArrayDeque<Iterator<? extends Interval>>();
        private Interval next;
        private final int depth;
        private final int maxDepth;

        private RecursiveIntervalIterator(int depth, int maxDepth) {
            this.depth = depth;
            this.maxDepth = maxDepth;
            next = advance();
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public Interval next() {
            if (next == null)
                throw new NoSuchElementException();
            Interval context = next;
            next = advance();
            return context;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        private Interval advance() {
            while (true) {
                if (iterator.hasNext()) {
                    Interval interval = iterator.next();
                    if (maxDepth == -1 || stack.size() < maxDepth) {
                        stack.push(iterator);
                        iterator = intervalExtractor.iterator(interval);
                    }
                    if (depth == -1 || (stack.size() == depth + 1)) {
                        return interval;
                    }
                } else if (!stack.isEmpty()) {
                    iterator = stack.poll();
                } else {
                    return null;
                }
            }
        }
    };
}
